
typedef int ElemType;

//算法的基本设计思想：
//分别求两个升序序列A、B的中位数，设为a和b，求序列A、B的中位数过程如下：
//1.若a=b，则a或b即为所求中位数，算法结束
//2.若a<b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等
//3.若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等
//在保留的两个升序序列中，重复过程1、2、3，直到两个序列中二次均只含一个元素时为止
//较小者即为所求的中位数
//算法的时间复杂度为O(log2n),空间复杂度为O(1)
ElemType SearchMid(ElemType A[], ElemType B[], int n) {
    int aStart = 0, aEnd = n - 1, bStart = 0, bEnd = n - 1;
    int aMid, bMid;
    while (aStart != aEnd && bStart != bEnd) {
        aMid = (aStart + aEnd) / 2;
        bMid = (bStart + bEnd) / 2;
        if (A[aMid] == B[aMid]) {
            return A[aMid];
        }
        if (A[aMid] < B[bMid]) {
            if ((aStart + aEnd) % 2 == 0) {
                aStart = aMid + 1;
            } else {
                aStart = aMid;
            }
            bEnd = bMid;
        } else {
            if ((bStart + bEnd) % 2 == 0) {
                bStart = bMid + 1;
            } else {
                bStart = bMid;
            }
            aEnd = aMid;
        }
    }
    return A[aStart] < B[bStart]? A[aStart] : B[bStart];
}